{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "geneSet = \" abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,\"\n",
    "target = \"Hello World!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "target = \"The world is changed. I feel it in the water. I feel it in the earth. \\\n",
    "I smell it in the air. Much that once was. is lost. For none now live who remember it.\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_parent(length):\n",
    "    genes = []\n",
    "    while len(genes) < length:\n",
    "        sampleSize = min(length - len(genes), len(geneSet))\n",
    "        genes.extend(random.sample(geneSet, sampleSize))\n",
    "    return ''.join(genes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_fitness(guess, target):\n",
    "    return sum(1 for expected, actual in zip(target, guess)\n",
    "               if expected == actual)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate(parent):\n",
    "    index = random.randrange(0, len(parent))\n",
    "    childGenes = list(parent)\n",
    "    newGene, alternate = random.sample(geneSet, 2)\n",
    "    childGenes[index] = alternate if newGene == childGenes[index] else newGene\n",
    "    return ''.join(childGenes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime\n",
    "def display(guess):\n",
    "    timeDiff = datetime.datetime.now() - startTime\n",
    "    fitness = get_fitness(target,guess)\n",
    "    print(\"{0}\\t{1}\\t{2}\".format(guess, fitness, str(timeDiff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed()\n",
    "startTime = datetime.datetime.now()\n",
    "bestParent = generate_parent(len(target))\n",
    "bestFitness = get_fitness(target,bestParent)\n",
    "display(bestParent)\n",
    "while True:\n",
    "    child = mutate(bestParent)\n",
    "    childFitness = get_fitness(target,child)\n",
    "    if bestFitness >= childFitness:\n",
    "        continue\n",
    "    display(child)\n",
    "    if childFitness >= len(bestParent):\n",
    "        break\n",
    "    bestFitness = childFitness\n",
    "    bestParent = child"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
